/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: tao
 * Date: 2023-11-03
 * Time: 19:37
 */

/**
 * 合并两个有序链表
 * https://leetcode.cn/problems/merge-two-sorted-lists/
 */
class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
class Solution {

    // public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    //     if(list1 == null) return list2;
    //     if(list2 == null) return list1;

    //     ListNode listnode = new ListNode();
    //     ListNode tmp = listnode;

    //     while(list1 != null && list2 != null) {
    //         if(list1.val <= list2.val) {
    //             tmp.next = list1;
    //             list1 = list1.next;
    //             tmp = tmp.next;
    //         } else {
    //             tmp.next = list2;
    //             list2 = list2.next;
    //             tmp = tmp.next;
    //         }
    //     }

    //     if(list1 != null) {
    //         tmp.next = list1;
    //     }
    //     if(list2 != null) {
    //         tmp.next = list2;
    //     }

    //     return listnode.next;
    // }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null) return list2;
        if(list2 == null) return list1;

        if(list1.val <= list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        }

        list2.next = mergeTwoLists(list2.next, list1);
        return list2;
    }
}
public class Test {

    public static void main(String[] args) {

    }
}
